COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00007 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a47.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Rice's Theorem \hfil}

\medskip
Let $P(M)$ be any statement about the input-output relation $R↓M$ of 
a TM,~$M$. Examples:

\medskip
\display 20pt:$\bullet$:
$P(M)$ is $xR↓My$, for particular $x$ and $y$.

\medskip
\display 20pt:$\bullet$:
The image (or inverse image) of $R↓M$ is empty/finite/infinite/equal to
a particular FML, CFL, or TML.

\medskip
\display 20pt:$\bullet$:
$R↓M$ is a function/a partial function/transitive/an equivalence relation/a
monotone function/ recursively enumerable/recursive.

\medskip
\display 20pt:$\bullet$:
For each $x$ there are infinitely many $y$ for which $xR↓My$.

\medskip
\display 20pt:$\bullet$:
And so on.

\medskip\noindent
If there are two machines $M↓1$ and $M↓2$ for which $P(M↓1)$,
$\neg P(M↓2)$, then there is no decision algorithm for $P(M)$.

\medskip\noindent
{\bf Proof.} Let $M↓0$ be a machine that has $R↓M=\emptyset$, for example
a~machine that, ignoring its input, goes into a loop. Suppose that
$P(M↓0)$. Let $\langle M↓3,x\rangle$ be an arbitrary halting problem. Build a deterministic
machine~$M↓4$, with $\langle M↓3,x\rangle$ built~in,
that searches for a computation of~$M↓3$ with input~$x$.
If it ever finds one, it then simulates~$M↓2$. If $M↓3$ never halts
on~$x$, $R↓{M↓4}=\emptyset=R↓{M↓0}$, so $P(M↓4)$. If $M↓3$ halts on~$x$,
$R↓{M↓4}=R↓{M↓2}$, so $\neg P(M↓4)$. If we could compute $P(M↓4)$,
we would have an algorithm to decide
if $M↓3$ halts on~$x$, absurd.

\medskip
\display 38pt::{\bf Drill:} What if $\neg P(M↓0)$?

\medskip
We conclude:

\proclaim Rice's Theorem. If $P$ is a decidable property of DTMs, that
depends only on the input-output relations, it is either true for all or
false for all, e.g., the property of computing a partial recursive or
non-p.r.\ function. If $P$ is a decidable property of NTMs, that
depends only on the input-output relations, it is either true for all
or false for all, e.g., the property of having a recursively enumerable
or non-r.e.\ input-output relation.

To sum it up, everything interesting about TMs is undecidable.



\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
May 28, 1986.
%revised date;
%subsequently revised.

\bye